import java.util.ArrayList;
import java.util.List;

public class FindAnagrams {
    //该代码有错误，窗口的维护问题未解决
    public List<Integer> code(String ss, String pp) {
        List<Integer> ret = new ArrayList<>();
        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();

        int[] hash1 = new int[26];
        for (char ch: p){
            hash1[ch - 'a']++;
        }

        int[] hash2 = new int[26];
        for (int left = 0, right = 0; right < s.length; right++){
            char ch = s[right];
            hash2[ch - 'a']++;
            Boolean flag = true;
            //出窗口
            if ((right - left + 1) > p.length){
                char removeCh = s[left];
                hash2[removeCh - 'a']--;
                left++;
            }

            for (int i = 0; i < 26; i++){
                if (hash2[i] != hash1[i]){
                    flag = false;
                    break;
                }
            }

            if (flag == true){
                ret.add(left);
            }

        }

        return ret;
    }
    public List<Integer> code2(String ss, String pp) {
        List<Integer> ret = new ArrayList<Integer>();
        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();
        int[] hash1 = new int[26];
        for (char ch : p){
            hash1[ch - 'a']++;
        }

        int[] hash2 = new int[26];
        int m = p.length;
        for (int left = 0, right = 0, count = 0; right < s.length; right++) {
            char in = s[right];
            // 进窗⼝ + 维护 count
            if (++hash2[in - 'a'] <= hash1[in - 'a'])
                count++;
            if (right - left + 1 > m) // 判断
            {
                char out = s[left++];
                // 出窗⼝ + 维护 count
                if (hash2[out - 'a']-- <= hash1[out - 'a'])
                    count--;
            }
            // 更新结果
            if (count == m)
                ret.add(left);
        }
        return ret;
    }
    public static void main(String[] args) {
        FindAnagrams test = new FindAnagrams();
        test.code("cbaebabacd", "abc");
    }
}
